package com.leetcode.algorithm.y22.m08.w2;

/**
 * 209. 长度最小的子数组
 * 
 * https://leetcode.cn/problems/minimum-size-subarray-sum/
 * 
 * @author jie.deng
 *
 */
class Question0209Solution01 {
	
	public int minSubArrayLen(int target, int[] nums) {
		int len = nums.length;
		// DP状态定义
		// dp[i]表示以nums[i]结尾的长度最小子数组的起点索引
		int[] dp = new int[len];
		// dpSum[i]表示以nums[i]结尾的长度最小子数组的和
		int[] dpSum = new int[len];

		// DP状态初始化
		dpSum[0] = nums[0];
		if (dpSum[0] >= target) {
			dp[0] = 1;
			return 1;
		} else {
			dp[0] = 0;
		}

		int min = len;
		for (int i = 1; i < len; i++) {
			if (nums[i] >= target) {
				dpSum[i] = nums[i];
				dp[i] = 1;
				return 1;
			} else {
				dpSum[i] = dpSum[i - 1] + nums[i];
				if (dpSum[i] < target) {
					dp[i] = 0;
				} else {
					int left = dp[i - 1];
					while (dpSum[i] - nums[left] >= target) {
						dpSum[i] -= nums[left++];
					}
					dp[i] = left;
					if ((i - dp[i] + 1) < min) {
						min = i - dp[i] + 1;
					}
				}
			}
		}

		return dpSum[len - 1] < target ? 0 : min;
	}
    
}